package com.jchy.maze;

import com.jchy.graph.Graph;
import com.jchy.graph.Vertex;
import com.jchy.graph.Edge;
import java.util.ArrayList;
import java.util.HashMap;
import org.apache.log4j.*;

public class Maze {

	private int maxX;
	private int maxY;
	
	private Graph possible;
	private Graph maze;
	
	/**
	 * @return the maze
	 */
	public Graph getMaze() {
		return maze;
	}

	/**
	 * @param maze the maze to set
	 */
	public void setMaze(Graph maze) {
		this.maze = maze;
	}

	/**
	 * @return the possible
	 */
	public Graph getPossible() {
		return possible;
	}

	/**
	 * @param possible the possible to set
	 */
	public void setPossible(Graph possible) {
		this.possible = possible;
	}

	public Maze(int inMaxX, int inMaxY)
	{
		maxX = inMaxX;
		maxY = inMaxY;
	}
	
	/**
	 * @return the maxX
	 */
	public int getMaxX() {
		return maxX;
	}

	/**
	 * @param maxX the maxX to set
	 */
	public void setMaxX(int maxX) {
		this.maxX = maxX;
	}

	/**
	 * @return the maxY
	 */
	public int getMaxY() {
		return maxY;
	}

	/**
	 * @param maxY the maxY to set
	 */
	public void setMaxY(int maxY) {
		this.maxY = maxY;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		Logger log = Logger.getLogger("com.jchy.maze.Maze.main");
		
		//Graph graphPossible; 
		//Graph mazeGraph;
		Maze aMaze;
		//int maxX = 30;
		//int maxY = 10;
		//int randomStart;
		//int randomEnd;
		//ArrayList<Vertex> visited = new ArrayList<Vertex>();

		log.info("In Main");
		
		aMaze = new Maze(30, 10);
		
		aMaze.buildGraphPossible();
		
		//randomStart = 1; /* (int)Math.floor(Math.random() * maxX) + 1; */
		//randomEnd = maxX; /* (int)Math.floor(Math.random() * maxX) + 1; */
		
		//Vertex start = getVertex(maxX, randomStart, 1);
		//Vertex end = getVertex(maxX, randomEnd, maxY);
		// Find Trail is not bad... it just does not guarantee a connection between
		// the start and end
		//System.out.print(String.valueOf(start.getId()));
		//findTrail(graphPossible, visited, mazeGraph, start, end);
		//System.out.println();
		
		//System.out.print(String.valueOf(start.getId()));
		//findTrail(graphPossible, visited, mazeGraph, start, end);
		//System.out.println();
		
		aMaze.buildMaze();

		//System.out.println("Start: " + String.valueOf(start.getId()) + " End: " + String.valueOf(end.getId()));
		//printGraphEdges(mazeGraph);
		
		aMaze.printMaze(1,30);
	}
	
	public void buildGraphPossible()
	{
		Logger log;
		possible = new Graph(Graph.BI_DIRECTIONAL);
		
		log = Logger.getLogger("com.jchy.maze.Maze.buildGraphPossible");
		
		for(int y = 1; y <= maxY; y++)
		{
			for(int x = 1; x <= maxX; x++)
			{
				log.debug("X: " + String.valueOf(x) + " Y: " + String.valueOf(y));
				Vertex currVertex = getVertex(x, y);
				if(y < maxY)
				{
					Vertex belowVertex = getVertex(x, y + 1);
					Edge currBelow = new Edge(currVertex, belowVertex);
					log.debug("y<maxY - Adding edge: " + currBelow.toString());
					possible.addEdge(currBelow);
				}
				if(x < maxX)
				{
					Vertex rightVertex = getVertex(x + 1, y);
					Edge currRight = new Edge(currVertex, rightVertex);
					log.debug("x<maxX - Adding edge: " + currRight.toString());
					possible.addEdge(currRight);
				}
			}
		}
	}
	
	public int getVertexId(int x, int y)
	{
		/* Example assumes maxX of 6 and maxY of 5 */
		/*   y\x   1   2   3   4   5   6   */
		/*   1     1   2   3   4   5   6   */
		/*   2     7   8   9  10  11  12   */
		/*   3    13  14  15  16  17  18   */
		/*   4    19  20  21  22  23  24   */
		/*   5    25  26  27  28  29  30   */
		int vertexId = (x - 1) + (y - 1) * maxX + 1;
		
		return vertexId;
	}
	
	public Vertex getVertex(int x, int y)
	{
		
		Vertex result;
		Integer vertexId = new Integer(getVertexId(x, y));
		result = new Vertex(vertexId.longValue());
		
		return result;
	}
	
	public int getXFromId(int inVertexId)
	{
		int result = 0;
		while(inVertexId > maxX)
		{
			inVertexId -= maxX;
		}
		result = Integer.valueOf(inVertexId);
		
		return result;
	}

	public int getYFromId(int inVertexId)
	{
		int result = 0;
		
		while(inVertexId > maxX)
		{
			inVertexId -= maxX;
			result += 1;
		}
		result += 1;
		
		return result;
	}
	
	public void buildMaze()
	{
		ArrayList<Vertex> possibleVertices;
		int vertexCount;
		int edgeCount;
		HashMap<Long,Long> components;
		int randomVertexNumber;
		Vertex randomVertex;
		long randomVertexComponent;
		long adjacentVertexComponent;
		ArrayList<Vertex> mazeVertices;
		ArrayList<Vertex> adjacentVertices;
		ArrayList<Vertex> adjacentVerticesDifferentComponents;
		int randomAdjacentVertexNumber;
		Vertex randomAdjacentVertex;
		Edge randomEdge;
		Logger log;
		long minComponent;
		ArrayList<Vertex> notLowestComponent;
		
		log = Logger.getLogger("com.jchy.maze.Maze.buildMaze");
		
		// start with a graph with all the vertices possible but no edges
		// this graph will have the same number of components as the number of vertices
		maze = new Graph(Graph.BI_DIRECTIONAL);
		possibleVertices = possible.getVertices();
		vertexCount=0;
		components = new HashMap<Long,Long>();
		for(Vertex aVertex: possibleVertices)
		{
			maze.addVertex(aVertex);
			vertexCount++;
		}
		
		// set each vertex to use it's id as it's component number
		// determine the lowest numbered component
		mazeVertices = maze.getVertices();
		minComponent=Long.MAX_VALUE;
		for(Vertex mazeVertex: mazeVertices)
		{
			components.put(new Long(mazeVertex.getId()), new Long(mazeVertex.getId()));
			if(mazeVertex.getId() < minComponent)
				minComponent=mazeVertex.getId();
		}
		
		
		log.debug("Possible Vertex Count: " + String.valueOf(vertexCount));
		
		edgeCount = 0;
		do
		{
			do 
			{
				// randomly select a vertex of one component (initially all vertices)
				// except the lowest numbered component
				mazeVertices = maze.getVertices();
				notLowestComponent = new ArrayList<Vertex>();
				for(Vertex mazeVertex: mazeVertices)
				{
					if(components.get(mazeVertex.getId()).longValue() != minComponent)
						notLowestComponent.add(mazeVertex);
				}
				randomVertexNumber = (int)Math.floor(Math.random() * notLowestComponent.size());
				randomVertex = notLowestComponent.get(randomVertexNumber);
				randomVertexComponent = components.get(new Long(randomVertex.getId())).longValue();
				log.debug("Random vertex: " + String.valueOf(randomVertex.getId()) + " Component: " + String.valueOf(randomVertexComponent));
				
				// review vertices which could be adjacent to this vertex 
				// find all vertices on a different component(s)
				// randomly select one of these
				// (select a different vertex if the selected vertex is not
				// adjacent to a vertex on a different component - like on all four sides)
				adjacentVertices = possible.getConnectedVertices(randomVertex);
				adjacentVerticesDifferentComponents = new ArrayList<Vertex>();
				for(Vertex adj: adjacentVertices)
				{
					adjacentVertexComponent = (components.get(new Long(adj.getId()))).longValue();
					log.debug("Random Vertex can be adjacent to: " + String.valueOf(adj.getId()) + " Component: " + String.valueOf(adjacentVertexComponent));
					if(adjacentVertexComponent != randomVertexComponent)
					{
						log.debug("Adjacent vertex added");
						adjacentVerticesDifferentComponents.add(adj);
					}
				}

			} while(adjacentVerticesDifferentComponents.size() == 0);
			
			randomAdjacentVertexNumber = (int)Math.floor(Math.random() * adjacentVerticesDifferentComponents.size());
			randomAdjacentVertex = adjacentVerticesDifferentComponents.get(randomAdjacentVertexNumber);
			
			// add an edge, count the two components of this edge as one component 
			// (change the component number of the vertices with the higher component number
			// to equal the component number of the vertex with the lower component number)
			// decrementing the number of components by one
			// repeat until the number of edges equals the number of possible vertices minus 1
			randomVertexComponent = components.get(new Long(randomVertex.getId())).longValue();
			adjacentVertexComponent = components.get(new Long(randomAdjacentVertex.getId())).longValue();
			if(randomVertexComponent > adjacentVertexComponent)
			{
				for(Vertex mazeVertex: mazeVertices)
				{
					if( (components.get(new Long(mazeVertex.getId())).longValue() == randomVertexComponent) )
						components.put(new Long(mazeVertex.getId()), new Long(adjacentVertexComponent));
				}
			}
			else 
			{
				for(Vertex mazeVertex: mazeVertices)
				{
					if( (components.get(new Long(mazeVertex.getId())).longValue() == adjacentVertexComponent) )
						components.put(new Long(mazeVertex.getId()), new Long(randomVertexComponent));
				}
			}
			randomEdge = new Edge(randomVertex, randomAdjacentVertex);
			maze.addEdge(randomEdge);
			edgeCount++;
			log.debug("Edge: " + String.valueOf(edgeCount) + " RandomVertex: " + String.valueOf(randomVertex.getId()) + " Adjacent: " + String.valueOf(randomAdjacentVertex.getId()));
		
		} while (edgeCount < (vertexCount - 1) );
		
	}

	public void findTrail(Graph inGraphPossible, ArrayList<Vertex> inVisited, Graph inMazeGraph, Vertex inCurr, Vertex inEnd)
	{
		
		boolean vertexVisited = false;
		for(Vertex aVertex: inVisited)
		{
			if(aVertex.equals(inCurr))
				vertexVisited = true;
		}
		
		if(!vertexVisited)
		{
			inVisited.add(inCurr);
		}
		
		ArrayList<Vertex> connects = inGraphPossible.getConnectedVertices(inCurr);
		ArrayList<Vertex> notVisitedConnects = new ArrayList<Vertex>();
		for(Vertex connect: connects)
		{
			boolean add = true;
			for(Vertex visited: inVisited)
			{
				if(visited.equals(connect))
					add = false;
			}
			if(add)
				notVisitedConnects.add(connect);
		}
		
		int size = notVisitedConnects.size();
		
		if(size > 0 && !inCurr.equals(inEnd))
		{
			int randomEdge = (int)Math.floor(Math.random() * size);
			Vertex next = notVisitedConnects.get(randomEdge);
			System.out.print(" to " + String.valueOf(next.getId()));
			Edge currNext = new Edge(inCurr, next);
			inMazeGraph.addEdge(currNext);
			findTrail(inGraphPossible, inVisited, inMazeGraph, next, inEnd);
		}
		
		
	}

	public static void printGraphEdges(Graph inGraph)
	{
		ArrayList<Edge> edges = inGraph.getEdges();
		for(Edge e: edges)
		{
			System.out.println(e);
		}
	}
	
	public void printMaze(int inStartX, int inEndX)
	{
		/* horiz line */
		System.out.print("@");
		for(int x = 1; x <= maxX; x++)
		{
			boolean connectedDown = false;
			if(x==inStartX)
				connectedDown = true;
			
			if(connectedDown)
				System.out.print(" ");
			else
				System.out.print("@");
			
			System.out.print("@");
		}
		System.out.println();

		/* Maze Body */
		for(int y = 1; y <= maxY; y++)
		{
			/* vert lines */
			System.out.print("@");
			for(int x = 1; x < maxX; x++)
			{
				Vertex curr = getVertex(x, y);
				boolean connectedRight = false;
				Vertex right = getVertex(x+1, y);
				Edge currRight = new Edge(curr,right);
				connectedRight = maze.isEdgeInList(currRight);

				if( connectedRight )
					System.out.print("  ");
				else 
					System.out.print(" @");
			}
			System.out.println(" @");
			
			/* horiz line */
			System.out.print("@");
			for(int x = 1; x <= maxX; x++)
			{
				Vertex curr = getVertex(x, y);
				boolean connectedDown = false;
				Vertex down = getVertex(x, y+1);
				Edge currDown = new Edge(curr,down);
				if(y == maxY)
				{
					if(x == inEndX)
						connectedDown = true;
					else
						connectedDown = false;
				}
				else 
					connectedDown = maze.isEdgeInList(currDown);
				
				if(connectedDown)
					System.out.print(" ");
				else
					System.out.print("@");
				
				System.out.print("@");
			}
			System.out.println();
			
		}
		
	}
	
}
